/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 *
 * https://leetcode-cn.com/problems/top-k-frequent-elements/description/
 *
 * algorithms
 * Medium (62.72%)
 * Likes:    1104
 * Dislikes: 0
 * Total Accepted:    268.1K
 * Total Submissions: 427.3K
 * Testcase Example:  '[1,1,1,2,2,3]\n2'
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * k 的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 * 
 * 
 * 
 * 
 * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 * 
 */

// @lc code=start
class Solution {
    // public:
    // class myComparision {
    //     public:
    //     bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
    //         return lhs.second > rhs.second;
    //     }
    // };
    // vector<int> topKFrequent(vector<int>& nums, int k) {

    //     unordered_map<int, int> map;
    //     for(int i = 0; i < nums.size(); i++){
    //         map[nums[i]]++;
    //     }

    //     //对频率进行排序，
    //     //定义一个小顶堆，大小为k;
    //     priority_queue<pair<int, int>, vector<pair<int, int>>, myComparision> pri_que;

    //     //用固定大小为k的小顶堆，扫描所有频率的数值
    //     for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
    //         pri_que.push(*it);
    //         if(pri_que.size() > k){
    //             pri_que.pop();
    //         }
    //     }

    //     //找出前k个高频元素，因为小顶堆先弹出的是小的，所以倒序来输出到数组
    //     vector<int> res(k);
    //     for(int i = k-1; i >= 0; i--){
    //         res[i] = pri_que.top().first;
    //         pri_que.pop();
    //     }
        
    //     return res;
    // }

public: 
    class MyCompare{
        public:
            bool operator() (const pair<int, int>& lhs, const pair<int , int>& rhs){
                return lhs.second > rhs.second;
            }
    };


public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        vector<int> res(k);

        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++){
            map[nums[i]]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, MyCompare> pri_que;

        for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
            pri_que.push(*it);
            if(pri_que.size() > k) {
                pri_que.pop();
            }
        }

        for(int i = k-1; i >= 0; i--){
            res[i] = pri_que.top().first;
            pri_que.pop();
        }

        return res;


    }

};
// @lc code=end

